package Tree;

import java.util.Stack;

/**
 * 题目 ：二叉搜索树迭代器
 * 题目详述 ：
 * 实现一个二叉搜索树迭代器类BSTIterator ，表示一个按中序遍历二叉搜索树（BST）的迭代器：
 *
 * （1）BSTIterator(TreeNode root) 初始化 BSTIterator 类的一个对象。
 *  BST 的根节点 root 会作为构造函数的一部分给出。指针应初始化为一个不存在于 BST 中的数字，且该数字小于 BST 中的任何元素。
 * （2）boolean hasNext() 如果向指针右侧遍历存在数字，则返回 true ；否则返回 false 。
 * （3）int next()将指针向右移动，然后返回指针处的数字。
 * 注意，指针初始化为一个不存在于 BST 中的数字，所以对 next() 的首次调用将返回 BST 中的最小元素。
 * 可以假设next()调用总是有效的，也就是说，当调用 next()时，BST 的中序遍历中至少存在一个下一个数字。
 *
 */
public class BSTIterator {
    /**
     *  核心思想 ：
     *  （1）可以对于所要遍历的二叉搜索树进行修改的话 ：
     *  即，可以通过将展开二叉搜索树，然后对于二叉搜索树从根节点开始遍历，直至遍历完二叉搜索树的所有节点；
     *  （2）不可以对于所要遍历的二叉搜索树进行修改的话 ：
     *  1.即，与上述展开二叉搜索树思路一致，可以在初始化迭代器的过程中，中序遍历二叉搜索树，定义一个链表来保存二叉搜索树中的所有节点；
     *  2.即，若是熟悉二叉树的中序遍历的话，即可以直接使用中序遍历过程中的方法，来实现next方法和hasNext方法；
     */

    TreeNode node;
    Stack<TreeNode> stack;
    // 二叉搜索树迭代器的初始化
    public BSTIterator(TreeNode root) {
        node = root;
        stack = new Stack<>();
    }

    // 二叉搜索树的中序遍历（从小到大遍历二叉搜索树中的节点）
    // next方法，每次都会去获取下一个节点值，所以直接调用中序遍历中while循环中对于每个节点操作即可
    public int next() {
        // 遍历到当前节点的左子树中的最左节点
        while(node != null){
            stack.push(node);
            node = node.left;
        }
        // 若是遍历到的节点为null，即获取栈中的元素；
        node = stack.pop();
        // next方法，所要返回的是当前遍历到的节点值
        int value = node.val;
        // 遍历右子树
        node = node.right;

        return value;
    }

    // 是否拥有下一个节点；
    // 二叉树中序遍历中，while循环每次循环都会去遍历二叉树的节点；
    public boolean hasNext() {
        return node != null || !stack.isEmpty();
    }
}
